/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.fa;

import java.util.Arrays;

/** For fixed text t, this automaton is able to decide whether a 
 *  given string s MIGHT be a suffix of t. That means, if the oracle's answer
 *  is no, then s is definitetly not a suffix of t, if the answer is yes,
 *  s might or might not be a suffix of t. The number of states 
 *  equals |t|+1 plus an additional FAIL state.*/
public class SuffixOracle implements CharacterAutomaton {

	private int alphabetSize;
	private int[] pattern;
	// transitions[sourceState][character] gives the target state
	private int[][] transitions;
	private int failState;
	
	public SuffixOracle(int alphabetSize, int[] pattern) {
		this.alphabetSize = alphabetSize;
		this.pattern = pattern;
		this.failState = pattern.length + 1;
		// initialize all transitions to ge to fail state
		transitions = new int[pattern.length+2][alphabetSize];
		for (int i=0; i<transitions.length; ++i) {
			Arrays.fill(transitions[i], failState);
		}
		// suff[i] contains the state corresponding to the longest suffix 
		// of pattern[0..i-1] that does not end in state i.
		int[] suff = new int[pattern.length+1];
		suff[0] = failState;
		for (int i=0; i<pattern.length; ++i) {
			// add "inner" transition
			transitions[i][pattern[i]] = i+1;
			// possible append characters to suffixes of pattern[0..i-1]
			// that do not end in state i
			for (int k = suff[i]; k!=failState; k=suff[k]) {
				int j = transitions[k][pattern[i]]; 
				if (j!=failState) {
					suff[i+1] = j;
					break;
				}
				transitions[k][pattern[i]] = i+1;
			}
		}
	}
	
	@Override
	public int getAlphabetSize() {
		return alphabetSize;
	}

	@Override
	public int getStartState() {
		return 0;
	}

	@Override
	public int getStateCount() {
		return pattern.length + 2;
	}

	@Override
	public int getTransitionTarget(int state, int character) {
		return transitions[state][character];
	}

	public int read(int[] string) {
		int state = getStartState();
		for (int c : string) {
			state = getTransitionTarget(state, c);
		}
		return state;
	}
	
	public boolean mightBeFactor(int[] string) {
		return mightBeFactor(read(string));
	}

	public boolean mightBeFactor(int state) {
		return state != failState;
	}

}
